contents

모리스 순회(Morris Traversal)는 공간 효율적인 이진 트리 순회 알고리즘입니다. 이 알고리즘의 가장 중요하고 주된 특징은 트리를 O(1) 공간 복잡도로 순회한다는 것입니다. 즉, 재귀(호출 스택 사용)나 명시적인 스택(표준적인 반복 순회 방식)을 사용하지 않습니다.

이는 순회 과정에서 트리의 구조를 임시로 변경하고, 경로를 추적하기 위해 임시 "스레드(thread)"를 만들었다가, 순회가 끝나면 원래 구조로 복원하는 방식으로 이를 달성합니다.

모리스 순회가 해결하는 문제

모리스 순회의 중요성을 이해하려면, 표준적인 순회 방법들과 그 공간 복잡도를 살펴봐야 합니다 (여기서 h는 트리의 높이이며, 최악의 편향 트리(skewed tree)에서는 O(n)이 될 수 있습니다).

모리스 순회는 바로 이 공간 문제를 해결하기 위해 개발되었습니다. O(n)의 시간 복잡도를 유지하면서 O(1)의 보조 공간만으로 트리를 순회하는 방법을 제공합니다.

핵심 아이디어: 스레드 이진 트리 💡

이 알고리즘은 스레드 이진 트리(threaded binary tree) 라는 아이디어에 기반합니다. 왼쪽 서브트리 방문 후 부모 노드로 돌아가기 위해 스택을 사용할 수 없으므로, 다시 위로 올라갈 다른 방법이 필요합니다.

모리스 순회는 왼쪽 서브트리에 있는 노드들의 right 포인터를 활용합니다. 왼쪽 서브트리의 가장 오른쪽 노드(즉, 중위 순회 선행자(inorder predecessor))는 일반적으로 right 포인터가 null을 가리킵니다. 이 알고리즘은 이 null 포인터를 임시로 변경하여, 서브트리의 루트(즉, 우리가 다시 돌아가야 할 노드)를 가리키도록 만듭니다.

비유: 미로를 탐색한다고 상상해 보세요. 빵 부스러기를 떨어뜨리는(스택 사용) 대신, 현재 위치에서 방금 지나온 이전 교차로로 실(thread)을 묶습니다. 막다른 길에 다다르면, 그 실을 따라 교차로로 돌아가고, 실을 푼 다음, 다른 길로 진행합니다.

이 임시 링크는 다음을 보장합니다.

  1. 왼쪽 서브트리로 내려갑니다.
  2. 왼쪽 서브트리 순회를 완료합니다.
  3. "스레드"를 따라 루트 노드로 다시 올라갑니다.
  4. 루트 노드를 방문합니다.
  5. 스레드를 제거합니다 (트리의 원래 구조 복원).
  6. 오른쪽 서브트리로 내려갑니다.

알고리즘: 중위 순회 (상세 단계)

중위 순회(왼쪽, 루트, 오른쪽)는 모리스 순회의 가장 직접적인 구현 방식입니다. 상세한 로직은 다음과 같습니다.

root에서 시작하는 current라는 단 하나의 포인터만 필요합니다.

초기화: current = root

While current가 null이 아닌 동안:
    
    // 경우 1: current의 왼쪽 자식이 없음
    If current.left가 null이면:
        1. current를 방문합니다 (예: current.value 출력).
        2. 오른쪽 자식으로 이동합니다: current = current.right.

    // 경우 2: current의 왼쪽 자식이 있음
    Else:
        1. current의 중위 순회 선행자를 찾습니다.
           (이는 current의 왼쪽 서브트리에서 가장 오른쪽에 있는 노드입니다)
           
           predecessor = current.left
           While (predecessor.right가 null이 아님) AND (predecessor.right가 current가 아님):
               predecessor = predecessor.right
           
        2. 선행자의 오른쪽 포인터를 확인합니다:

           // 하위 경우 2a: 이 서브트리를 처음 방문함.
           // 선행자의 오른쪽 포인터가 여전히 null임.
           If predecessor.right가 null이면:
               // 임시 스레드 생성
               predecessor.right = current
               // 순회를 계속하기 위해 왼쪽 자식으로 이동
               current = current.left
           
           // 하위 경우 2b: 두 번째 방문.
           // 우리가 만든 스레드를 통해 왼쪽 서브트리에서 돌아옴.
           Else (predecessor.right가 current이면):
               // 스레드 제거 (트리 복원)
               predecessor.right = null
               // 왼쪽 서브트리를 마쳤으므로, 이제 루트를 방문
               current를 방문합니다 (예: current.value 출력).
               // 오른쪽 자식으로 이동
               current = current.right

변형: 전위 및 후위 순회

동일한 기본 알고리즘을 영리하게 수정하여 전위 및 후위 순회를 생성할 수 있습니다.

전위 순회 (루트, 왼쪽, 오른쪽)

이는 중위 순회 알고리즘을 약간 수정한 것입니다. 전위 순회에서는 서브트리를 탐색하기 전에 노드를 방문합니다.

이는 왼쪽 자식이 없는 노드의 일반적인 방문에 더해, 스레드를 생성하는 순간(왼쪽으로 가기 직전)에 current 노드를 방문함으로써 달성할 수 있습니다.

수정 사항:

후위 순회 (왼쪽, 오른쪽, 루트)

후위 순회는 훨씬 더 복잡합니다. 노드는 왼쪽과 오른쪽 서브트리 _모두_를 방문한 후에 방문되어야 합니다.

O(1) 공간 복잡도로 이를 달성하는 가장 일반적이고 영리한 방법은 다음과 같습니다.

  1. 루트, 오른쪽, 왼쪽 순서로 방문하는 수정된 전위 순회를 만듭니다.
  2. 각 노드를 방문할 때마다 연결 리스트의 _앞_에 추가합니다 (또는 역순으로 출력).
  3. 최종 결과 [루트, 오른쪽, 왼쪽]을 뒤집으면 [왼쪽, 오른쪽, 루트]가 되며, 이는 올바른 후위 순회입니다.

이를 구현하려면 위에서 언급한 전위 순회 알고리즘에서 "왼쪽"과 "오른쪽" 로직을 맞바꾸기만 하면 됩니다. 이는 일반적인 해결책이지만 혼란스러울 수 있습니다. 더 직접적이지만 복잡한 방법은 스레드가 제거될 때 왼쪽 서브트리의 오른쪽 경계 포인터들을 순회하며 역순으로 방문하는 것을 포함하며, 이는 매우 고급 기법으로 간주됩니다.

복잡도 분석

장단점

references